package 链表.环形链表II_142;
import 链表.两两交换链表中的节点_24.Solution.ListNode;

import java.util.HashSet;
import java.util.Set;

/*
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路：
    一. 双指针法
    1. 判断是否有环
    2. 判断环在哪
    1.判断有环用快慢指针就行，有环就会在环中循环走，那么二者就会相遇
    2. 判断环在哪可以用二者走的步数进行某种计算，就能找到入口
    二、hash法
    我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。
*/
public class Solution {
    public static void main(String[] args) {
        ListNode[] head = new ListNode[4];
        head[3] = new ListNode(-4,null);
        head[2] = new ListNode(0,head[3]);
        head[1] = new ListNode(2,head[2]);
        head[0] = new ListNode(3,head[1]);
        System.out.println(head[1].val);
    }
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head; // 慢指针走一步
        ListNode fast = head; // 快指针走两步
        while (fast != null && fast.next != null){  //判断顺序一定不能反
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                ListNode meet = slow; // 记录fast和slow相遇的节点meet
                ListNode start = head;
                // slow = head; // 另一个指针从头开始走
                while (start != meet){
                    start = start.next;  //
                    meet = meet.next;
                }
                return start;
            }
        }
        return null;
    }

    // 方法2 hash法，一直遍历，如果遍历到头没有重复的set值就输出null，有重复的就输出该值
    public static ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        for (ListNode i = head; i != null; i = i.next){
            if (!set.contains(i)){
                set.add(i);
            } else {
                return i;
            }
        }
        return null;
    }
}
